public class Solution688 {
    public double knightProbability(int n, int k, int row, int column) {
        int[] dx={-2,-1,1,2,-2,-1,1,2};
        int[] dy={-1,-2,2,1,1,2,-2,-1};
        double[][] f=new double[n][n];
        f[row][column]=1.0;
        for (int i=0;i<k;i++){
            double[][] g=new double[n][n];
            for (int j=0;j<n;j++){
                for (int l=0;l<n;l++){
                    if (f[j][l]!=0){
                        for (int d=0;d<8;d++){
                            int x=j+dx[d];
                            int y=l+dy[d];
                            if (valid(x,y,n)){
                                g[x][y]+=0.125*f[j][l];
                            }
                        }
                    }
                }
            }
            f=g;
        }
        double ans=0;
        for (int i=0;i<n;i++){
            for (int j=0;j<n;j++){
                ans=ans+f[i][j];
            }
        }
        return ans;
    }

    private boolean valid(int x, int y, int n) {
        return x>=0 && y>=0 && x<n && y<n;
    }

    public static void main(String[] args) {
        System.out.println(new Solution688().knightProbability(3,2,0,0));
    }
}
